/*
	Copyright (c) 2008, Grant Jones <grant@podtronics.com>.
	All rights reserved.

	Redistribution and use in source and binary forms, with or
	without modification, are permitted provided that the following
	conditions are met:

		Redistributions of source code must retain the above copyright
		notice, this list of conditions and the following disclaimer.
		
		Redistributions in binary form must reproduce the above copyright
		notice, this list of conditions and the following disclaimer in
		the documentation and/or other materials provided with the
		distribution.
		
		Neither the name of the gxjones.com nor the names of its
		contributors may be used to endorse or promote products derived
		from this software without specific prior written permission.
	
	THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
	"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
	LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
	FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
	COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
	INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
	(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
	SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
	HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
	STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
	ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
	OF THE POSSIBILITY OF SUCH DAMAGE.
	
	http://www.opensource.org/licenses/bsd-license.php
*/

/*
 *  radixtree_enum.c
 *  radixtree
 *
 *  Created by Grant Jones on 3/5/08.
 *
 */

#include "radixtree.h"
#include "radixtree_enum.h"


int rt_enum_add_branchs( rtenum_t *rte, off_t loc, int is_root_tag )
{
	TagStruct *tag = tagm_readTag( rte->rt->tms, loc, 1 );
	rt_bit_string_t *key_frag = NULL;
	cmapStruct *visit_list;
	int i;
	
	assert(tag->data);
	assert(tag->hdr.dlen == RTREE_BRANCH_PTRS_SZ);
	
	if( !is_root_tag )
		key_frag = rtree_bits_dup( (rt_bit_string_t *)tag->key );
	
	visit_list = cmap_new(rte->key_stack->mempool);
	
	for( i = 0; i < 2; i ++ )
	{
		if(((off_t *) tag->data)[i] == 0ULL)
			continue;
			
		rtenum_entry_t *loc_ptr = cmap_assign_new(visit_list, cmap_gethighestkey(visit_list)+1, sizeof(rtenum_entry_t) );
		if(!loc_ptr)
			return -1;
		
		loc_ptr->tag_loc = ((off_t *) tag->data)[i];
		loc_ptr->key_frag = key_frag;
	}
	cmap_assign(rte->key_stack, cmap_gethighestkey(rte->key_stack)+1, visit_list );

	tagm_freeTag(tag);
	return 0;
}

int rt_enum_all_begin( rtree_t *rt, rtenum_t *rte, mempool_t *pool )
{
	rte->rt = rt;
	rte->key_stack = cmap_new(pool);
	rte->key_name_stack = cmap_new(rte->key_stack->mempool);
	
	/* prime the visit list stack */
	/* read root tag: */
	rt_enum_add_branchs( rte, rt->list_cursor, 1 );

	rte->depth = 0;
	return 0;
}


int rt_enumerate_nextkey( rtenum_t *rte, rtvalue_t *key )
{
	rtenum_entry_t *next_loc;
	TagStruct *tag;
	off_t tag_loc;
	cmapStruct *visit_list;
	int loc_idx;
	int stack_top;
	
	for(;;)
	{
		/* find the next location to visit */
		for(;;)
		{
			stack_top = cmap_gethighestkey(rte->key_stack);
			visit_list = cmap_lookup( rte->key_stack, stack_top );
			
			if(!visit_list)	
				return 1;	/* done */
			
			loc_idx = cmap_gethighestkey( visit_list );
	//			printf("loc_idx: %d\n", loc_idx );
			next_loc = cmap_lookup( visit_list, loc_idx );

			if(next_loc)	
				break;		/* found the next location */
			
			/* remove the empty location list */
			cmap_remove(rte->key_stack, stack_top);
			cmap_remove(rte->key_name_stack, stack_top);
		}

		/* remove the location (we are handling it right now) */
		cmap_remove(visit_list, loc_idx);

	//		printf("rt_enumarte_next: next_loc = %ld\n", (int)*next_loc );
		
		rt_enum_add_branchs( rte, next_loc->tag_loc, 0 );
			
		/* paste together the key: */
		/* a separate stack is maintained for the key name because of the 
		way this non-recursive enumeration traverses the tree -- mainly parts
		are removed from the key_stack queue at times when we need them...
		as usual there may be better less memory intensive ways to do this */
		
		cmap_assign( rte->key_name_stack, stack_top, next_loc );
		cmapEnumStruct e;
		CMAP_KEY_TYPE k;
		rtenum_entry_t *d;
		rt_bit_string_t *key_bstr = NULL;
		size_t j;
		key->size = 0;
		key->data = NULL;
		cmap_enum(rte->key_name_stack, &e);
		while( (d = cmap_enum_next( &e, &k )) )
		{
			if( d->key_frag == 0 )
				continue;
			key_bstr = rtree_bits_concat(key_bstr, d->key_frag);
		}
		if( key_bstr == NULL )
			continue;
		key->size = rt_bstr_sz( key_bstr );
		key->data = key_bstr->d;
		printf("ENUM key_bstr->len: %d\n", (int)key_bstr->len );
		printf("ENUM key_bstr->d: " );		
		fwrite(key_bstr->d, key->size, 1, stdout);
		printf("\n");
	}
	return 0;
}
	


/* ************************************************************************
************************************************************************ */
/*!
	@function rt_enumerate_begin
	@abstract Enumerate all keys with prefix specified by key (key may be
		empty, in which case the whole tree is enumerated)
	@discussion Enumeration will obtain only the key value
	@param rt
	@param rte
	@param pool Pool to allocate from, may be NULL
	@param key
	@result
*/

int rt_enumerate_begin( rtree_t *rt, rtenum_t *rte, mempool_t *pool, rtvalue_t *key )
{
#ifdef BROKEN_IN_THIS_VERSION
	rt_bit_string_t *key_left;
	int locate_result;
	size_t last_step_loc;
	off_t last_loc = rt->list_cursor;
	
	rte->rt = rt;
	rte->key_stack = cmap_new(pool);
	rte->key_name_stack = cmap_new(rte->key_stack->mempool);
	if( key->size > 0 )
	{
		rt_bit_string_t *key_bstr;
		key_bstr = rtree_bits_from_bytes( key->data, key->size );		/* XXX: makes a duplicate of key in memory */
		assert( key_bstr );
	
//		printf("locating partial key\n");
		last_loc = rt_locate_key( rt, key_bstr, &last_step_loc, &key_left, &locate_result );
//		printf("last loc: %ld, locate_result: %d\n", (int)last_loc, locate_result );

		if( locate_result < 0 )	/* error */
			return -1;
		if( locate_result != 1 )		/* make sure a complete match was found */
			return 0;
		/* TODO: enumeration could possibly go off a partial key match */
		if( key_left )
			assert( key_left->len == 0 );	/* until we support partial keys, use this assertion */
	}

	/* prime the visit list stack */
	cmapStruct *visit_list = cmap_new(rte->key_stack->mempool);
	
	rtenum_entry_t *loc_ptr = cmap_assign_new(visit_list, cmap_gethighestkey(visit_list)+1, sizeof(rtenum_entry_t)+key->size );
	if(!loc_ptr)
		return -1;
	loc_ptr->tag_loc = last_loc;
	loc_ptr->key_frag_sz = key->size;
	memcpy( loc_ptr->key_frag, key->data, key->size );
	
	cmap_assign(rte->key_stack, cmap_gethighestkey(rte->key_stack)+1, visit_list  );
	
	rte->depth = 0;
	return 0;
#endif
	return -1;
}


int rt_enumerate_next( rtenum_t *rte, rtvalue_t *key, rtvalue_t *data )
{
#ifdef BROKEN_IN_THIS_VERSION
	data->size = 0;
	data->data = NULL;
	while( data->size == 0 )
	{
		rtenum_entry_t *next_loc;
		TagManagerEnumStruct tmes;
		TagStruct *tag;
		off_t tag_loc;
		cmapStruct *visit_list;
		int loc_idx;
		int stack_top;
		
		/* find the next location to visit */
		for(;;)
		{
			stack_top = cmap_gethighestkey(rte->key_stack);
			visit_list = cmap_lookup( rte->key_stack, stack_top );
			
			if(!visit_list)	
				return 1;	/* done */
			
			loc_idx = cmap_gethighestkey( visit_list );
//			printf("loc_idx: %d\n", loc_idx );
			next_loc = cmap_lookup( visit_list, loc_idx );

			if(next_loc)	
				break;		/* found the next location */
			
			/* remove the empty location list */
			cmap_remove(rte->key_stack, stack_top);
			
			cmap_remove(rte->key_name_stack, stack_top);
		}




		/* remove the location (we are handling it right now) */
		cmap_remove(visit_list, loc_idx);

//		printf("rt_enumarte_next: next_loc = %ld\n", (int)*next_loc );
		
		visit_list = cmap_new(rte->key_stack->mempool);	
		
		
		if( tagm_beginEnumTags( rte->rt->tms, &tmes, next_loc->tag_loc ) )
			return -1;

		while( (tag = tagm_nextTag( rte->rt->tms, &tmes, &tag_loc )) )
		{
			if( tag->hdr.bFlags & TAG_OVERFLOW )		/* we accumulate overflow tags */
			{
//				printf("rt_enumerate_next: accumulating data of size: %ld\n", tag->hdr.dlen );
				
//				data->data = realloc( data->data, data->size+tag->hdr.dlen );
				data->data = mempool_realloc_named(rte->key_stack->mempool, data->data, data->size+tag->hdr.dlen, "rt_enumerate_next data" );

				memcpy( &((char *)data->data)[data->size], tag->data, tag->hdr.dlen );
				data->size += tag->hdr.dlen;
				continue;
			}
			if( tag->hdr.klen == 0 )
				continue;

			rtenum_entry_t *loc_ptr = cmap_assign_new(visit_list, cmap_gethighestkey(visit_list)+1, sizeof(rtenum_entry_t)+tag->hdr.klen );
			loc_ptr->tag_loc = tag_loc;
			loc_ptr->key_frag_sz = tag->hdr.klen;
			memcpy( loc_ptr->key_frag, tag->key, tag->hdr.klen );		
		
//			printf("rt_enumerate_next: need to visit loc %ld\n", (int)tag_loc );
		}

		tagm_endEnumTags(rte->rt->tms, &tmes);

		cmap_assign(rte->key_stack, cmap_gethighestkey(rte->key_stack)+1, visit_list  );				
		
		/* paste together the key: */
		if( data->size > 0 )
		{
			/* a separate stack is maintained for the key name because of the 
			way this non-recursive enumeration traverses the tree -- mainly parts
			are removed from the key_stack queue at times when we need them...
			as usual there may be better less memory intensive ways to do this */
			
			cmap_assign( rte->key_name_stack, stack_top, next_loc );
			cmapEnumStruct e;
			CMAP_KEY_TYPE k;
			rtenum_entry_t *d;
			size_t j;
			key->size = 0;
			key->data = NULL;
			cmap_enum(rte->key_name_stack, &e);
			while( (d = cmap_enum_next( &e, &k )) )
				key->size += d->key_frag_sz;

			if( key->size > 0 )
			{
				j = 0;
				key->data = mempool_malloc_named(rte->key_stack->mempool, key->size, "rt_enumerate_next key" );
				if(!key->data)
					return -1;
					
				cmap_enum(rte->key_name_stack, &e);
				while( (d = cmap_enum_next( &e, &k )) )
				{
					memcpy( &((char *)key->data)[j], d->key_frag, d->key_frag_sz );
					j += d->key_frag_sz;
				}
			}
		}
		
	}

	return 0;
#endif	
	return -1;
}
	

int rt_enumerate_end( rtenum_t *rte )
{
	return 0;
}



